Міністерство освіти та науки України Національний університет “Львівська політехніка” Кафедра ПЗ Курсова робота з курсу “Методи та засоби комп`ютерних інформаційних технологій” Стиснення інформації методом Хаффмана Керівник:  Львів - 2007 Завдання до курсової роботи Тема курсової роботи: Стиснення інформації алгоритмом RLE. Постановка задачі: Розробити програму для архівування та розархівування файлів алгоритмом RLE. Програмний продукт має надавати користувачу можливості архівувати файли, розархівовувати бути зручним та ефективним у використанні. Анотація “ Стиснення інформації алгоритмом RLE ”. Курсова робота. – НУ “Львівська політехніка”, каф.: ПЗ, дисципліна: “Методи та засоби комп`ютерних інформаційних технологій”, 2007. Курсова робота складається з сторінок, таблиці, додатку. В даній курсовій роботі спроектовано та розроблено програму для стиснення інформації алгоритмом RLE. Проект надає можливості архівування файлів та їх розархівування алгоритмом RLE. Зміст Завдання до курсової роботи .2 Анотація .3 Вступ .6 1. Аналітичний огляд ............................................................................7 1.1 Способи стиснення інформації.....................................................6 1.2 Огляд алгоритмів стиснення інформації .......................................7 1.2.1 Метод RLE……..................................................................8 1.2.2 Статичне кодування Хаффмана………………...................9 1.2.3 Арифметичне кодування…................................................9 1.2.4 Алгоритм Лемпеля-Зіва……............................................10 2. Постановка задачі та обгрунтування вибраного напряму проектування .............12 3. Проектний розділ.................................................................................13 4. Дослідницький розділ..........................................................................24 5. Технологічний розділ...........................................................................25 Висновки....................................................................................................27 Література.................................................................. ...............................28 Додаток 1....................................................................................................29 Вступ Дані, вироблені різноманітними програмами, зберігаються на зовнішніх пристроях, що запам'ятовують, обсяг яких обмежений. При передачі даних через канали зв'язку, пропускна здатність каналу обмежена. Перебороти деякі з цих обмежень дозволяють алгоритми стиску. Дані, що зберігаються на ЗЗП, можна стискувати, тим самим як би збільшуючи ємкість ЗП. Це актуально при резервному копіюванні інформації. Пропускна здатність каналів зв'язку при використанні стиски також збільшується. Основна ідея стиску інформації - використання того факту, що дані містять повторювані ланцюжки символів, а також нерівномірність статистичного розподілу алфавіту вихідних даних. Методи стиску даних мають достатньо довгу історію. Існує ряд простих підходів до даної проблеми. Найбільше відомий - це кодування довжин ланцюжків (RLE). Суть методу: заміна ланцюжків повторюваних символів на один цей символ і лічильник повторення. Проблема складається в тому, щоб розпаковщик міг відрізнити в результуючому потоку таку кодовану серію від інших символів. Розв'язання очевидне - постачати всі такі ланцюжки деякими заголовками: Наприклад, використовувати перший бита як ознака кодованої серії або використовувати для цієї цілі який-небудь символ. Метод достатньо ефективний для графічних зображень. 1. Аналітичний відділ. 1.1 Способи стиснення інформації Running - це найпростіший з методів упаковки інформації . Припустимо що маємо рядок тексту, і в кінці рядка коштує 40 пропусків. Проблема стиснення цього рядка вирішується дуже просто - ці 40 пробілів ( 40 байт ) стискаються в 3 байт...